"The Most Beautiful Program Ever Written" - Using Python's new match Statement

TLDR: The full source code of The Most Beautiful Program Ever Written implemented with a Python match statement can be found here.

William Byrd presented the The Most Beautiful Program Ever Written (YouTube), which basically is a lambda calculus interpreter that uses an environment instead of the typical β-reduction. I very much encourage you to learn about this program, as it is a very cool piece of software (watch his presentation on YouTube or check out Alberto Zaccagni’s post).

Here’s his original code:

(define eval-expr
  (lambda (expr env)
    (pmatch expr
      [`,x (guard (symbol? x))
        (env x)]
      [`(lambda (,x) ,body)
        (lambda (arg)
          (eval-expr body (lambda (y)
                            (if (eq? x y)
                                arg
                                (env y)))))]
      [`(,rator ,rand)
       ((eval-expr rator env)
        (eval-expr rand env))])))

And here is my version written with Python’s match statement, which is a new feature added with Python 3.10:

def evalexpr(expr, env):
    match expr:
        case S() as x:
            return env(x)
        case (S('λ'), x, body):
            return lambda arg: \
                evalexpr(body, lambda y: \
                    arg if x == y else env(y))
        case (rator, rand):
            return evalexpr(rator, env) \
                (evalexpr(rand, env))
        case _ as x:
            return x

As you can see, it is created as closely as feasible to the original code. The main difference are symbols, as Python does not have an equivalent feature. The solution is to implement a class such as the following:

class S:
    __match_args__ = ['s']

    def __init__(self, s):
        self.s = s
    def __eq__(self, s):
        return self.s == s
    def __repr__(self):
        return self.s
    def __str__(self):
        return self.s

λ = S('λ')
assert S('λ') == λ

This class, named S for symbol, is a simple class storing a string, which is its representation. Equal symbols have equal representation strings. This is tested with the last two lines.

To check my code I created the following tests. As you can see, the function evalexpr has the basic properties expected by a lambda calculus interpreter.

empty_env = lambda x: f'Lookup Error: {x}'

A, B, x, y = S('A'), S('B'), S('x'), S('y')
assert evalexpr(A, empty_env) == empty_env('A')
assert evalexpr(A, lambda _: A) == A
assert evalexpr((λ, x, x), empty_env)('test') == 'test'
assert evalexpr((λ, x, (λ, x, x)), empty_env)(A)(B) == B
assert evalexpr((λ, x, (λ, y, x)), empty_env)(A)(B) == A
assert evalexpr((λ, x, (λ, y, y)), empty_env)(A)(B) == B
assert evalexpr(((λ, x, x), 1), empty_env) == 1
assert evalexpr((((λ, x, (λ, y, x)), 1), 2), empty_env) == 1
assert evalexpr((((λ, x, (λ, y, y)), 1), 2), empty_env) == 2

And that is it for the basic interpreter! Nothing more is needed. It is Turing-complete, numbers and Booleans could be implemented using Church encoding.

However, to have “nice” results (in the domain of Python) and to directly use functions like addition, the interpreter must be extended. The following code snippets extend the program, such that it allows the usage of an if-than-else-statement and Python operators.

As a matter of fact, the interpreter can easily be extended by list functions and other native functions. The result would be a basic Lisp interpreter.

# Import operator and add symbols
import operator
ifel, lt, add, sub = S('ifel'), S('lt'), S('add'), S('sub')

# Add ifel, and operator cases to evalexpr
        case (ifel, t, c, a):
            return evalexpr(c, env) if evalexpr(t, env) \
                else evalexpr(a, env)
        case (op, *args) if op in dir(operator):
            return getattr(operator, str(op)) \
                (*[evalexpr(a, env) for a in args])

# Add an addition test
assert evalexpr((add, 1, 2), empty_env) == 3

The second case statement in the previous snippet is especially interesting. It checks if the operation symbol can be found in Python’s operator module. If the module contains the operation it fetches the relevant function and calls it with all arguments of the evalexpr call.

I use this extension to implement a simple Fibonacci number generator. I makes use of the Y-combinator and a Fibonacci implementation found here.

f, g, a = S('f'), S('g'), S('a')

Y = evalexpr((λ, f, \
                ((λ, g, (g, g)), \
                    (λ, g, \
                        (f, (λ, a, ((g, g), a)))))), empty_env)

fib = evalexpr((Y, (λ, f, \
                    (λ, x, \
                        (ifel, (lt, x, 2), \
                            x, \
                            (add, (f, (sub, x, 2)), \
                                  (f, (sub, x, 1))))))), empty_env)

assert [fib(i) for i in range(15)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

To sum up, Python’s new match statement is very powerful and allows the writing of very clean and beautiful code. Writing your own interpretation of The Most Beautiful Program Ever Written gives you a deep insight in the lambda calculus, interpreters and computability. It was a nice challenge and I enjoyed it very much.

Once again, the full source code can be found here.